package leetcode_1701_1800;

import java.util.Arrays;

public class LeeCode_1799 {
    public static void main(String[] args) {
        System.out.println(maxScore(new int[]{3,4,6,8}));
        System.out.println(maxScore(new int[]{1,2,3,4,5,6}));
    }
    private static int maxScore(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int[][] gcd = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                gcd[i][j] = gcd(nums[i], nums[j]);
            }
        }
        int all = 1 << n;
        int[] dp = new int[all];
        for (int i = 1; i < all; i++){
            int c = Integer.bitCount(i);
            if ((c & 1) == 1)
                continue;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0){
                    for (int k = j + 1; k < n; k++) {
                        if ((i & (1 << k)) != 0){
                            dp[i] = Math.max(dp[i], dp[i ^ (1 << j) ^ (1 << k)] + gcd[j][k] * (c / 2));
                        }
                    }
                }
            }
        }
        return dp[all - 1];
    }
    private static int gcd(int x, int y){
        while (x != 0){
            int tmp = x;
            x = y % x;
            y = tmp;
        }
        return y;
    }
}